1 /*
2 * Copyright (C) 2012 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.collect;
18
19 import static com.google.common.collect.CollectPreconditions.checkRemove;
20 import static com.google.common.collect.Maps.keyOrNull;
21
22 import com.google.common.annotations.Beta;
23
24 import java.util.Iterator;
25 import java.util.NavigableMap;
26 import java.util.NavigableSet;
27 import java.util.NoSuchElementException;
28 import java.util.SortedMap;
29
30 /**
31 * A navigable map which forwards all its method calls to another navigable map. Subclasses should
32 * override one or more methods to modify the behavior of the backing map as desired per the <a
33 * href="http://en.wikipedia.org/wiki/Decorator_pattern">decorator pattern</a>.
34 *
35 * <p><i>Warning:</i> The methods of {@code ForwardingNavigableMap} forward <i>indiscriminately</i>
36 * to the methods of the delegate. For example, overriding {@link #put} alone <i>will not</i>
37 * change the behavior of {@link #putAll}, which can lead to unexpected behavior. In this case, you
38 * should override {@code putAll} as well, either providing your own implementation, or delegating
39 * to the provided {@code standardPutAll} method.
40 *
41 * <p>Each of the {@code standard} methods uses the map's comparator (or the natural ordering of
42 * the elements, if there is no comparator) to test element equality. As a result, if the comparator
43 * is not consistent with equals, some of the standard implementations may violate the {@code Map}
44 * contract.
45 *
46 * <p>The {@code standard} methods and the collection views they return are not guaranteed to be
47 * thread-safe, even when all of the methods that they depend on are thread-safe.
48 *
49 * @author Louis Wasserman
50 * @since 12.0
51 */
52 public abstract class ForwardingNavigableMap<K, V>
53 extends ForwardingSortedMap<K, V> implements NavigableMap<K, V> {
54
55 /** Constructor for use by subclasses. */
56 protected ForwardingNavigableMap() {}
57
58 @Override
59 protected abstract NavigableMap<K, V> delegate();
60
61 @Override
62 public Entry<K, V> lowerEntry(K key) {
63 return delegate().lowerEntry(key);
64 }
65
66 /**
67 * A sensible definition of {@link #lowerEntry} in terms of the {@code lastEntry()} of
68 * {@link #headMap(Object, boolean)}. If you override {@code headMap}, you may wish to override
69 * {@code lowerEntry} to forward to this implementation.
70 */
71 protected Entry<K, V> standardLowerEntry(K key) {
72 return headMap(key, false).lastEntry();
73 }
74
75 @Override
76 public K lowerKey(K key) {
77 return delegate().lowerKey(key);
78 }
79
80 /**
81 * A sensible definition of {@link #lowerKey} in terms of {@code lowerEntry}. If you override
82 * {@link #lowerEntry}, you may wish to override {@code lowerKey} to forward to this
83 * implementation.
84 */
85 protected K standardLowerKey(K key) {
86 return keyOrNull(lowerEntry(key));
87 }
88
89 @Override
90 public Entry<K, V> floorEntry(K key) {
91 return delegate().floorEntry(key);
92 }
93
94 /**
95 * A sensible definition of {@link #floorEntry} in terms of the {@code lastEntry()} of
96 * {@link #headMap(Object, boolean)}. If you override {@code headMap}, you may wish to override
97 * {@code floorEntry} to forward to this implementation.
98 */
99 protected Entry<K, V> standardFloorEntry(K key) {
100 return headMap(key, true).lastEntry();
101 }
102
103 @Override
104 public K floorKey(K key) {
105 return delegate().floorKey(key);
106 }
107
108 /**
109 * A sensible definition of {@link #floorKey} in terms of {@code floorEntry}. If you override
110 * {@code floorEntry}, you may wish to override {@code floorKey} to forward to this
111 * implementation.
112 */
113 protected K standardFloorKey(K key) {
114 return keyOrNull(floorEntry(key));
115 }
116
117 @Override
118 public Entry<K, V> ceilingEntry(K key) {
119 return delegate().ceilingEntry(key);
120 }
121
122 /**
123 * A sensible definition of {@link #ceilingEntry} in terms of the {@code firstEntry()} of
124 * {@link #tailMap(Object, boolean)}. If you override {@code tailMap}, you may wish to override
125 * {@code ceilingEntry} to forward to this implementation.
126 */
127 protected Entry<K, V> standardCeilingEntry(K key) {
128 return tailMap(key, true).firstEntry();
129 }
130
131 @Override
132 public K ceilingKey(K key) {
133 return delegate().ceilingKey(key);
134 }
135
136 /**
137 * A sensible definition of {@link #ceilingKey} in terms of {@code ceilingEntry}. If you override
138 * {@code ceilingEntry}, you may wish to override {@code ceilingKey} to forward to this
139 * implementation.
140 */
141 protected K standardCeilingKey(K key) {
142 return keyOrNull(ceilingEntry(key));
143 }
144
145 @Override
146 public Entry<K, V> higherEntry(K key) {
147 return delegate().higherEntry(key);
148 }
149
150 /**
151 * A sensible definition of {@link #higherEntry} in terms of the {@code firstEntry()} of
152 * {@link #tailMap(Object, boolean)}. If you override {@code tailMap}, you may wish to override
153 * {@code higherEntry} to forward to this implementation.
154 */
155 protected Entry<K, V> standardHigherEntry(K key) {
156 return tailMap(key, false).firstEntry();
157 }
158
159 @Override
160 public K higherKey(K key) {
161 return delegate().higherKey(key);
162 }
163
164 /**
165 * A sensible definition of {@link #higherKey} in terms of {@code higherEntry}. If you override
166 * {@code higherEntry}, you may wish to override {@code higherKey} to forward to this
167 * implementation.
168 */
169 protected K standardHigherKey(K key) {
170 return keyOrNull(higherEntry(key));
171 }
172
173 @Override
174 public Entry<K, V> firstEntry() {
175 return delegate().firstEntry();
176 }
177
178 /**
179 * A sensible definition of {@link #firstEntry} in terms of the {@code iterator()} of
180 * {@link #entrySet}. If you override {@code entrySet}, you may wish to override
181 * {@code firstEntry} to forward to this implementation.
182 */
183 protected Entry<K, V> standardFirstEntry() {
184 return Iterables.getFirst(entrySet(), null);
185 }
186
187 /**
188 * A sensible definition of {@link #firstKey} in terms of {@code firstEntry}. If you override
189 * {@code firstEntry}, you may wish to override {@code firstKey} to forward to this
190 * implementation.
191 */
192 protected K standardFirstKey() {
193 Entry<K, V> entry = firstEntry();
194 if (entry == null) {
195 throw new NoSuchElementException();
196 } else {
197 return entry.getKey();
198 }
199 }
200
201 @Override
202 public Entry<K, V> lastEntry() {
203 return delegate().lastEntry();
204 }
205
206 /**
207 * A sensible definition of {@link #lastEntry} in terms of the {@code iterator()} of the
208 * {@link #entrySet} of {@link #descendingMap}. If you override {@code descendingMap}, you may
209 * wish to override {@code lastEntry} to forward to this implementation.
210 */
211 protected Entry<K, V> standardLastEntry() {
212 return Iterables.getFirst(descendingMap().entrySet(), null);
213 }
214
215 /**
216 * A sensible definition of {@link #lastKey} in terms of {@code lastEntry}. If you override
217 * {@code lastEntry}, you may wish to override {@code lastKey} to forward to this implementation.
218 */
219 protected K standardLastKey() {
220 Entry<K, V> entry = lastEntry();
221 if (entry == null) {
222 throw new NoSuchElementException();
223 } else {
224 return entry.getKey();
225 }
226 }
227
228 @Override
229 public Entry<K, V> pollFirstEntry() {
230 return delegate().pollFirstEntry();
231 }
232
233 /**
234 * A sensible definition of {@link #pollFirstEntry} in terms of the {@code iterator} of
235 * {@code entrySet}. If you override {@code entrySet}, you may wish to override
236 * {@code pollFirstEntry} to forward to this implementation.
237 */
238 protected Entry<K, V> standardPollFirstEntry() {
239 return Iterators.pollNext(entrySet().iterator());
240 }
241
242 @Override
243 public Entry<K, V> pollLastEntry() {
244 return delegate().pollLastEntry();
245 }
246
247 /**
248 * A sensible definition of {@link #pollFirstEntry} in terms of the {@code iterator} of the
249 * {@code entrySet} of {@code descendingMap}. If you override {@code descendingMap}, you may wish
250 * to override {@code pollFirstEntry} to forward to this implementation.
251 */
252 protected Entry<K, V> standardPollLastEntry() {
253 return Iterators.pollNext(descendingMap().entrySet().iterator());
254 }
255
256 @Override
257 public NavigableMap<K, V> descendingMap() {
258 return delegate().descendingMap();
259 }
260
261 /**
262 * A sensible implementation of {@link NavigableMap#descendingMap} in terms of the methods of
263 * this {@code NavigableMap}. In many cases, you may wish to override
264 * {@link ForwardingNavigableMap#descendingMap} to forward to this implementation or a subclass
265 * thereof.
266 *
267 * <p>In particular, this map iterates over entries with repeated calls to
268 * {@link NavigableMap#lowerEntry}. If a more efficient means of iteration is available, you may
269 * wish to override the {@code entryIterator()} method of this class.
270 *
271 * @since 12.0
272 */
273 @Beta
274 protected class StandardDescendingMap extends Maps.DescendingMap<K, V> {
275 /** Constructor for use by subclasses. */
276 public StandardDescendingMap() {}
277
278 @Override
279 NavigableMap<K, V> forward() {
280 return ForwardingNavigableMap.this;
281 }
282
283 @Override
284 protected Iterator<Entry<K, V>> entryIterator() {
285 return new Iterator<Entry<K, V>>() {
286 private Entry<K, V> toRemove = null;
287 private Entry<K, V> nextOrNull = forward().lastEntry();
288
289 @Override
290 public boolean hasNext() {
291 return nextOrNull != null;
292 }
293
294 @Override
295 public java.util.Map.Entry<K, V> next() {
296 if (!hasNext()) {
297 throw new NoSuchElementException();
298 }
299 try {
300 return nextOrNull;
301 } finally {
302 toRemove = nextOrNull;
303 nextOrNull = forward().lowerEntry(nextOrNull.getKey());
304 }
305 }
306
307 @Override
308 public void remove() {
309 checkRemove(toRemove != null);
310 forward().remove(toRemove.getKey());
311 toRemove = null;
312 }
313 };
314 }
315 }
316
317 @Override
318 public NavigableSet<K> navigableKeySet() {
319 return delegate().navigableKeySet();
320 }
321
322 /**
323 * A sensible implementation of {@link NavigableMap#navigableKeySet} in terms of the methods of
324 * this {@code NavigableMap}. In many cases, you may wish to override
325 * {@link ForwardingNavigableMap#navigableKeySet} to forward to this implementation or a subclass
326 * thereof.
327 *
328 * @since 12.0
329 */
330 @Beta
331 protected class StandardNavigableKeySet extends Maps.NavigableKeySet<K, V> {
332 /** Constructor for use by subclasses. */
333 public StandardNavigableKeySet() {
334 super(ForwardingNavigableMap.this);
335 }
336 }
337
338 @Override
339 public NavigableSet<K> descendingKeySet() {
340 return delegate().descendingKeySet();
341 }
342
343 /**
344 * A sensible definition of {@link #descendingKeySet} as the {@code navigableKeySet} of
345 * {@link #descendingMap}. (The {@link StandardDescendingMap} implementation implements
346 * {@code navigableKeySet} on its own, so as not to cause an infinite loop.) If you override
347 * {@code descendingMap}, you may wish to override {@code descendingKeySet} to forward to this
348 * implementation.
349 */
350 @Beta
351 protected NavigableSet<K> standardDescendingKeySet() {
352 return descendingMap().navigableKeySet();
353 }
354
355 /**
356 * A sensible definition of {@link #subMap(Object, Object)} in terms of
357 * {@link #subMap(Object, boolean, Object, boolean)}. If you override
358 * {@code subMap(K, boolean, K, boolean)}, you may wish to override {@code subMap} to forward to
359 * this implementation.
360 */
361 @Override
362 protected SortedMap<K, V> standardSubMap(K fromKey, K toKey) {
363 return subMap(fromKey, true, toKey, false);
364 }
365
366 @Override
367 public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
368 return delegate().subMap(fromKey, fromInclusive, toKey, toInclusive);
369 }
370
371 @Override
372 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
373 return delegate().headMap(toKey, inclusive);
374 }
375
376 @Override
377 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
378 return delegate().tailMap(fromKey, inclusive);
379 }
380
381 /**
382 * A sensible definition of {@link #headMap(Object)} in terms of
383 * {@link #headMap(Object, boolean)}. If you override {@code headMap(K, boolean)}, you may wish
384 * to override {@code headMap} to forward to this implementation.
385 */
386 protected SortedMap<K, V> standardHeadMap(K toKey) {
387 return headMap(toKey, false);
388 }
389
390 /**
391 * A sensible definition of {@link #tailMap(Object)} in terms of
392 * {@link #tailMap(Object, boolean)}. If you override {@code tailMap(K, boolean)}, you may wish
393 * to override {@code tailMap} to forward to this implementation.
394 */
395 protected SortedMap<K, V> standardTailMap(K fromKey) {
396 return tailMap(fromKey, true);
397 }
398 }